\chapter{文件发送与接收}
本章介绍先后尝试的三种传输模型:``一问一答''、`并发处理''、``多此迭代''。
最终通过分析综合考虑选择使用``多次迭代''。

这一章由于涉及到的概念并非十分具体因此为了更好的表述做以下约定:
\begin{itemize}
	\item S为发送者。
	\item $R_x$为接收者，如$R_1，R_2$等。
	\item 涉及的文件拥有N块数据\footnote{FInfo.chunknum字段的值。}。
	\item 当前发送的文件块\footnote{即之前介绍的Chunk结构。}为$C_x (0<x<N)$。
	\item 文件块请求以$B_x$\footnote{与之前介绍的Bill有关。}为一组，
		一组包含0～32块请求$0 < x < N/32$。
	\item 最大文件区域的值 $n = N/32$
\end{itemize}
所有文件传输模型均只考虑一对多的方式即一个发送者多个接收者。

\section{一问一答}
采用请求发送模式，R发送需要的文件块到网络中，S收到后发送文件块到网络。
但由于是一对多的发送方式，一份文件可能有多个接收者，导致S重复发送文件块。

例如，一个节点$R_1$开始请求数据后，文件传输途中另外一节点$R_2$发送请求
通讯过程如下:
\begin{enumerate}
	\item $R_1$ 发送$B_1，B_2，\ldots，B_n$ 到网络中;
	\item S收到$B_1\sim B_n$ 后开始发送
		$CB_1，CB_2，\ldots，CB_i (i < n)$;
	\item 在S 未发送完毕时，$R_2$ 开始请求下载，发送
		$B_1，B_2，\ldots，B_n$ 到网络中;
	\item S在发送完 $CB_n$ 后继续发送$CB_1，\ldots，B_i$，
		此时$R_1，R_2$都已经拥有完整的文件拷贝;
	\item S继续发送$CB_{i+1}，\ldots，CB_n$到网络中，此时所发数据会
		无故占用网络带宽;
\end{enumerate}

\section{多次迭代}
因此不能使用这种简单的一问一答的方式发送文件块，必须设计一种``智能''的发送方式。

把种方式称做``多次迭代''是因为S只处理比PCR值大的文件块请求，
小于这个值的请求则直接忽略直到没有文件块可传则结束本轮传输。

对于发送者S制定如下规则:
\begin{itemize}
	\item
		维护一个当前文件发送状态STATE 取值范围: BEGIN、SENDING、END
		STATE默认状态为END; \\
		在END状态下$R_x$收到SB命令S转换为BEGIN状态;\\
		在BEGIN状态下收到$B_x$转换为SENDING状态; \\
		在SENDING状态下发送$B_n$之后转换为END状态;
	\item 维护一个指向当前发送文件区域的指针PCR(Point to Current Region)，取值范
		围:$0\leq PCR\leq N/32$;\\
		PCR的值仅在SENDING状态下有效; \\
		PCR的值根据收到的最大$B_x$设置，如先后收到
		$B_1，B_2，B_3，B_8，B_4$则PCR的状态先后为1，2，3，8，8;
	\item 在收到$B_x$后若x<=PCR则忽略此$B_x$请求;
	\item 在END状态下忽略一切$B_x$请求;
	\item 从SENDING转换为END时候发送SE;
\end{itemize}


对于接收者$R_x$制定如下规则:
\begin{itemize}
	\item 请求开始时发送SB指令后发送$B_i\ldots B_j$到网络，
		其中$0 \leq i \le j \leq N/32$;
	\item $B_x$请求顺序必须按照升序排列;
	\item 在收到所缺区域中值最大的区域时结束请求。例如所缺文件区
		域为$B1，B2，B3，B4$，当前已经接收到$CB1，CB2$。如果此时接
		收到$CB_4$则直接结束，虽然$CB_3$暂时未收到;

	\item 在收到SE的时候结束当前请求;
	\item 在结束请求后若文件未下载完成则重新开始请求;
	\item 发送的$B_x$序列必须包含$B_n$若不需要此区域的文件块可发送空的$B_n$;
\end{itemize}

按照设定的规则之后，再来看之前遇到的问题:
\begin{enumerate}
	\item $R_1$ 发送$SB$，$B_1，B_2，\ldots，B_n$到网络中;
	\item $S$在收到$SB$后从END状态转换为BEGIN状态，收到$B_1$后从BEGIN转换为
		SENDING状态，并设置PCR=1，在收到$B_2$后设置PCR=2，\ldots 设置PCR=x;
	\item 在S{\em 未}发送完毕时，$R_2$开始请求下载，发送SB，$B_1，B_2，\ldots，B_n$到网络中;
	\item 由于S在SENDING状态忽略SB命令，收到$B_1$，小于PCR=x忽略，$B_2$，
		小于PCR=x忽略;
	\item S在发送完$CB_n$后PCR=n，因此忽略队列之后的请求，
		此时$R_1$拥有完整拷贝，$R_2$拥有$CB_x$之后的拷贝;
	\item $R_1$收到$CB_n$后完成下载退出通讯;$R_2$则结束当前请求发送SE，
		S收到后状态转化为END;
	\item 由于$R_2$结束请求后检测还有未完成的文件块，因此重新开始建立请求，
		发送SB，$B_1，B_2，\ldots，B_{x-1}$;
	\item 此时网络退化为点对点传送\footnote{如果之前有n个$R_x$则
		根据退出数量y蜕化为1对n-y传输。};
\end{enumerate}

不过发送$B_x$的速度很快，例如一个1G的文件根据系统的设
定ChunkSize=60000b，一个Bill最多可携带32块Chunk，一个
Bill的大小是16+16+32=64b，因此所需数据量是，
$(1G/60000b/32)*64=35，791b$ 只有30多Kb在局域网内相对
于人的操作是瞬间完成的。因此更多的时候是这种情况: S
收到的数据是这样
\begin{align*}
	SB，B_1，B_2，\cdots，B_n\\
	SB，B_1，B_2，\cdots，B_n\\
	SB，B_1，B_2，\cdots，B_n\\
\end{align*}
则S对应的处理序列是:发送$CB_1，\cdots，CB_n$后忽略之后队列中所有的$B_x$和SB
此时大部分$R_x$都已经在收到$CB_n$后完成下载。

但由于丢包的原因可能导致部分$R_x$还有少部分数据块未接收到。
这些$R_x$在收到SE后结束当前请求，并根据下载规则重新请求下载。
之后S收到的数据是这样:
\begin{align*}
	SB，B_{x1}，B_{x2}，B_{x8}，B_n         	(R_1)\\
	SB，B_{x2}，B_{x7}，B_{x8}，B_{x10}，B_n 	(R_2)\\
	SB，B_{x3}，B_{x4}，B_{x6}，B_n 			(R_3)\\
	\\
	其中x1 \leq x2 \leq x3 \cdots xn，但x1不一定和x2是相邻关系。
\end{align*}

S会根据之前的规则处理
$SB，B_{x1}，B_{x2}，B_{x8}，B_{x10}$
其中后面的SB和$B_{x7}，B_{x3}，B_{x4}，B_{x6}$等都被忽略。
$R_1$在收到$B_{x8}$后完成下载;
$R_2$在收到SE后发送SB，$B_{x7}，B_{x10}，B_n$到网络;
$R_3$在收到SE后发送SB，$B_{x3}，B_{x4}，B_{x6}，B_n$到网络;\\
此时S收到以下序列:
\begin{align*}
	SB，B_{x7}，B_{x10}，B_n，SB，B_{x3}，B_{x4}，B_{x6}，B_n
\end{align*}
处理完毕后$R_2$收到所有的文件块结束下载，$R_3$依然没收到任何数据，但收到SE后重
新发送SB，$B_{x3}，B_{x4}，B_{x6}，B_n$ 到网络中，此后完成所有发送过程。

以上过程发生概率虽然不算罕见，但发生时所缺少的$B_x$量一般都会很小因此虽然处理过程
复杂但会很快完成。及时在最坏情况下也会至少处理一个$B_x$请求。而局域网内一般只会几十
人下载收敛速度会非常快。
并且其中$R_3$的数据是特意构造导致前几次的迭代过程中没有收到任何有效的文件块，但
如果分析实际情况，$R_3$所缺少的文件块很可能与其他$R_x$大部分相同。原因在于所缺少的
文件块部分是因为丢包造成的。

如果以上过程中发送的$B_n$因为网络原因丢包了，如果是$R_1$的$B_n$丢包了则会加
快处理速度，因为$R_2$的$B_{x10}$可以不用等待下一次迭代就发送完毕。如果是$R_2$或者
$R_3$的$R_n$丢包了则会导致S和R都停止工作。

因此需要保证S在无事可做时尽快进入END以便通知$R_x$此轮请求结束，同时也需要保证
$R_x$有接收到S发送的SE指令。否则可能导致S和R都在等待对方的信息。
为了防止这种情况的发生，S和R都有一个定时器，S在SENDING状态下一定时间内若没有
发送任何$CB_x$则自动进入END状态。R在一定时间内没有收到文件块也会自动结束当前
请求。

对于文件的发送接收有一个重要原则，宁可让一个$R_x$重新发送全部的$B_x$也不能发送
一块无效的文件块，因为一个文件块就有60000B，而且一般一次发送32块，即使按照平均
长度一次无效的文件块发送也会导致960K的浪费。而前面有计算过1G的文件也只有30K
的$B_x$数据。
而造成重复$B_x$的原因是发送$B_x$的数据量小导致发送速度非常快，往往一个$CB_x$
都还没发送完毕所有$R_x$的$B_x$就已经进入到了S的处理队列中，因此S的队列中有非常
多的重复$B_x$，必须使用一个指针来指名当前位置，到达最后位置的时候就
将队列中所有数据全部抛弃(绝大部分都是重复无效的数据)让$R_x$重新发送请求。

\section{并发处理}
之前还尝试过另外一种模式，使用一个map记录当前系统所缺少的文件块(根据$B_x$来维护
这个map)，则如果接收到重复的$B_x$后由于已经有记录了就直接抛弃处理。
这种模式可以很好的解决部分问题，但在实现中必须使用多线程，发送线程和
处理$B_x$线程且需要共享这个map结构，较为麻烦。
且同样需要加入超时机制防止R、S停止工作，重新设
计一种方案，重新请求由于丢包导致$R_x$没有接收到的文件块。可以使用超时重传但效率
过低。而上面讨论的方案由于有多个$B_n$的冗余保证了快速重传(只要不是最后一个$B_n$
丢包了则不会影响效率相反由于$B_n$的丢包导致之后的$B_x$可以继续发送(需要大小PCR的
$B_x$); 

两种方案都可以尽量减少错误的重发文件块，前者通过消耗更多的流量来达到重传机
制，后者虽然不消耗多余的流量但需要消耗宝贵的时间。但在局域网中宝贵的资源是带
宽而不是流量，如果使用超时机制来实现重传则其实在浪费时间的同时浪费了大量的带
宽，因此在最初选择后者之后改为选择前者来实现本工具。
